1. Field of the Invention
The present invention relates to a multiprocessor system including a plurality of processors which execute tasks in parallel, and a method for executing tasks in the multiprocessor system.
2. Description of the Related Art
In recent years, multiprocessor systems have attracted attention as one approach for enhancing the performance of parallel processing of a common computer. The type of multiprocessor system configuration which is most frequently adopted is called a shared-memory type, in which a plurality of processors are connected to one bus so as to share a main storage device.
In such a multiprocessor system, a plurality of processor chips are usually mounted on a printed circuit board. Therefore, the speed of communication and synchronization between processors, which utilizes buses, is slower than the processing speeds of the processors. Therefore, such a multiprocessor system is used in the ease where the processing time of tasks (which are individual units of processing) is sufficiently larger than the time required for the communication and synchronization between processors. Such tasks, consisting of a few thousand instructions or more, are said to have a medium to large coarseness degree. By thus increasing the unit of processing (i.e., increasing the coarseness degree), the time required for the communication and synchronization between processors becomes small relative to the actual execution of the task.
In addition, the integration techniques for semiconductor devices have been rapidly improving in recent years. As a result, it has become possible to incorporate a large number of functional units and memories within one chip. Applied to multiprocessor systems, incorporating a plurality of processors in one chip will become possible in the future. In such cases, the bus connected to the processors will also be included in the chip, so that tasks of a broader range of coarseness degrees can be executed in the chip by the enhancement of the speed of communication and synchronization between processors. In other words, parallel-processing of a few dozen to a few thousand instructions is deemed to be possible. It is predicted that parallel-processing of such tasks (having small coarseness degrees) will form a main-stream in the future. One reason thereof is that so-called object-oriented programming and programming based on function-type languages, which have recently attracted a large attention, are in line with "parallel-processing tasks of small coarseness degrees".
On the other hand, a plurality of tasks are to be assigned to a limited number of processors in a multiprocessor system, so that it is commonplace to determine the execution order of tasks and appropriately select tasks to be assigned to particular processors. In order to realize this operation in a dynamic manner, a task which is waiting to be axqcuto is first stored in a task management device, e.g., a primary storage, and thereafter idle processors are detected. If an idle processor exists, one of the tasks waiting to be executed is selected to be executed and is assigned to the idle processor. The task selection is performed for the purpose of minimizing the execution time of the entire job. The process of determining the execution order of tasks and determining which tasks should be assigned to which processors is called scheduling, and various algorithms with different determination methods are known for such scheduling processes. In another process method, when a task to be executed is generated through task generation, that task is registered in a task management device as a task waiting for execution.
FIG. 12 is a diagram showing the operation of a conventional method of processor assignment for a multiprocessor system. In FIG. 12, the processor 2 generates a task 4, which is registered in the task management device as a task waiting to be executed. When the processor 0 detects that the processor 1 is "idle", one of the tasks in the task management device waiting to be executed is selected in accordance with a given scheduling algorithm, and is assigned to the processor 1 by the processor 0. At this time, the processor 0 is performing the scheduling process and the processor 2 is performing the task registration process.
This is true of a method described in Japanese Laid-Open Patent Publication No. 63-208948, where an idle processor (corresponding to the processor 1 in FIG. 12) monitors task ready queue (the task management device in FIG. 12) so as to automatically take out a task waiting to be executed. An "idle" processor is similarly performing a scheduling process.
Another method is described in No. 62-190548, where a processor which entrusted a task to another processor monitors the state of the task in the entrusted processor, so that when the entrusted processor's completion of the task is detected, another task is selected and assigned to the entrusted processor, which has become idle. In this method, the processor which entrusted a task to the other processor performs the process of monitoring the state of the entrusted processor.
The scheduling process, the task registration process, and the process of monitoring an entrusted processor described above can all be considered to be an overhead until the task is assigned to a processor and executed, that is, an overhead accompanying task processes, although meant for different purposes. FIG. 13 is a timing diagram showing the process time of tasks and the overhead processing time. As shown in FIG. 13, the overhead processing time is small relative to the actual task execution time in tasks having medium to large coarseness degrees, so that the overhead processing time is negligible.
However, when tasks of small coarseness degrees are parallel-processed by enhancing the speed of communication and synchronization between processors in a multiprocessor system having an overhead inherent to the above-described task processing, the. overhead processing time becomes large relative to the task processing time.
FIG. 14 is a timing diagram showing the process time of tasks and the overhead processing time of a task having a small coarseness degree. As shown in FIG. 14, the overhead processing time is large relative to the actual task execution time in tasks having medium to large coarseness degrees, so that the overhead processing time becomes unnegligible. As a result, the processing time of the entire job becomes large.